/*************************************************************************
	> File Name: 107.二叉树的层序遍历II.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 三  9/15 12:42:35 2021
 ************************************************************************/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
 #define max 1024
int** levelOrderBottom(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }

    struct TreeNode **queue = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * max);
    int head = 0, tail = 0, count = 0, level = 0;

    *returnColumnSizes = malloc(sizeof(int) * max);//一维数组
    int **ans = (int **)malloc(sizeof(int *) * max);

    queue[tail++] = root;
    count++;

    while (head != tail) {
        count = tail - head; //每层节点个数
        (*returnColumnSizes)[level] = count; //记录level层的节点个数
        ans[level] = malloc(sizeof(int) * count);//开辟空间存储每一层的每个节点
    
        for (int i = 1; i <= count; i++) {
            struct TreeNode *p = queue[head++];
            ans[level][i - 1] = p->val;
            if (p->left) queue[tail++] = p->left;
            if (p->right) queue[tail++] = p->right;
        }
        level++;
    }
    *returnSize = level;

    for (int i = 0, j = level- 1; i < j; i++, j--) {
        //交换层
        int *temp1 = ans[i];
        ans[i] = ans[j];
        ans[j] = temp1;
        //交换每一层的节点个数
        int *temp2 = (*returnColumnSizes)[i];
        (*returnColumnSizes)[i] = (*returnColumnSizes)[j];
        (*returnColumnSizes)[j] = temp2;
    }

    return ans;

}
